package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/search-in-a-binary-search-tree/">二叉搜索树中的搜索(Search in a Binary Search Tree)</a>
 * <p>给定二叉搜索树（BST）的根节点 root 和一个整数值 val。</p>
 * <p>你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入：root = [4,2,7,1,3], val = 2
 *                  4
 *                 / \
 *                <a color="blue">2</a>   7
 *               / \
 *              <a color="blue">1</a>   <a color="blue">3</a>
 *      输出：[2,1,3]
 *
 * 示例 2:
 *      输入：root = [4,2,7,1,3], val = 5
 *                  4
 *                 / \
 *                2   7
 *               / \
 *              1   3
 *      输出：[]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>数中节点数在 [1, 5000] 范围内</li>
 *     <li>1 <= Node.val <= 10^7</li>
 *     <li>root 是二叉搜索树</li>
 *     <li>1 <= val <= 10^7</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/11 10:47
 */
public class LC0700SearchInBinarySearchTree_S {

    public TreeNode searchBST(TreeNode root, int val) {
        //return searchBSTByIterator(root, val);
        return searchBSTByRecursion(root, val);
    }

    private TreeNode searchBSTByIterator(TreeNode currNode, int val) {
        while (currNode != null) {
            if (currNode.val == val) {
                return currNode;
            }
            if (currNode.val > val) {
                currNode = currNode.left;
            } else {
                currNode = currNode.right;
            }
        }
        return null;
    }

    private TreeNode searchBSTByRecursion(TreeNode currNode, int val) {
        if (currNode == null || currNode.val == val) {
            return currNode;
        }
        if (currNode.val > val) {
            return searchBSTByRecursion(currNode.left, val);
        } else {
            return searchBSTByRecursion(currNode.right, val);
        }
    }
}
